package com.rgs.se.data.tree.bst;

import com.rgs.se.data.queue.ArrayQueue;
import lombok.Data;

/**
 * @author Ren Gaoshuai
 * @ClassName BST
 * 二分搜索树
 * @date 2022-04-13 10:58
 **/
@Data
public class BST<E extends Comparable<E>> {

    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }


    public int getSize() {
        return size;
    }

    public boolean ieEmpty() {
        return size == 0;
    }

//    public void add(E e){
//        if (root == null){
//            root = new Node(e);
//            size++;
//        }else{
//            add(root,e);
//        }
//
//    }
//
//    private void add(Node node,E e){
//        if (node.e.equals(e)){
//            return ;
//        }else if(e.compareTo(node.e) < 0 && node.left == null){
//            //左
//            node.left = new Node(e);
//            size++;
//            return ;
//        }else if(e.compareTo(node.e) > 0 && node.right == null){
//            //右
//            node.right = new Node(e);
//            size++;
//            return;
//        }
//
//        if(e.compareTo(node.e) < 0 ){
//            add(node.left,e);
//        }else{
//            add(node.right,e);
//        }
//
//
//    }

    /**
     * 插入元素e digui简单写法
     */
    public void add(E e) {
        root = add(root, e);
    }

    //返回插入e元素后的node根节点
    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        //不管以node节点为根的树咋样，都返回node
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;

    }

    /**
     * 查看树中是否包含该元素
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else {
            return contains(node.right, e);
        }
    }

    /**
     * 树的前序遍历
     * 前序 中序 后续
     */
    public void preErgodic() {
        preErgodic(root);
    }

    private void preErgodic(Node node) {
        if (node == null) {
            return;
        }

        //这里的顺序就是前序 中序 后续
        System.out.println(node.e);
        preErgodic(node.left);
        preErgodic(node.right);
    }

    /**
     * 树的层次遍历，吃能借助队列采用非递归
     */
    public void breadth() {
        ArrayQueue<Node> queue = new ArrayQueue<>();
        queue.enQueue(root);
        while (!queue.isEmpty()) {
            Node cur = queue.deQueue();
            System.out.println(cur.e);
            if (cur.left != null) {
                queue.enQueue(cur.left);
            }
            if (cur.right != null) {
                queue.enQueue(cur.right);
            }
        }
    }

    /**
     * 找到最小值
     * 左子树一直向下遍历
     */
    public Node min() {
        if (root == null) {
            throw new IllegalArgumentException("bst is empty");
        }
        Node cur = root;
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;

    }

    private Node min(Node node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);

    }

    /**
     * 找到最大值
     * 右子树一直向下遍历
     */
    public Node max() {
        if (root == null) {
            throw new IllegalArgumentException("bst is empty");
        }
        Node cur = root;
        while (cur.right != null) {
            cur = cur.right;
        }
        return cur;

    }

    private Node max(Node node) {
        if (node.right == null) {
            return node;
        }
        return max(node.right);
    }

    public Node removeMin() {
        Node ret = min();
        root = removeMin(root);
        return ret;
    }

    /**
     * 返回删除节点后，新的树的根
     */
    private Node removeMin(Node node) {
        //递归结束，node为最小节点，把该节点的右节点挂载node的位置
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public Node removeMax() {
        Node ret = min();
        root = removeMax(root);
        return ret;
    }

    /**
     * 返回删除节点后，新的树的根
     */
    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 使用后继节点删除
     * 该方法返回删除节点e后的树根。
     */
    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {
            //找到了待删除的元素
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //只有右孩子
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //既有左孩子 又有右孩子
            //1. 找到他的后继节点
            Node success = min(node.right);
            //2.给后继节点赋值
            success.right = removeMin(node.right);
            //3.左子树不变
            success.left = node.left;
            //4.将删除的节点为null
            node.left = node.right = null;
            return success;

        }
    }

    /**
     * 使用前驱节点删除
     * 该方法返回删除节点e后的树根。
     */
    private Node remove2(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) < 0) {
            //左子树递归
            node.left = remove2(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            //右子树递归
            node.right = remove2(node.right, e);
            return node;
        } else {
            //相等 找到了删除的元素
            //只有左子树
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //只有右子树
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //都有
            //1.找到前驱节点
            Node success = max(node.left);
            //2.删除前驱结点
            success.left = removeMax(node.left);
            success.right = node.right;
            node.right = null;
            return success;
        }
    }

    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
        bst.removeMax();
        bst.preErgodic();

    }


}
